Thuật toán Fortune có thể xây dựng sơ đồ Voronoi cho n điểm trên mặt phẳng trong thời gian O(n log(n))[1].

Sơ đồ Voronoi của n điểm trong không gian Euclide d chiều đòi hỏi O ( n ⌈ d / 2 ⌉ ) {\displaystyle O(n^{\lceil d/2\rceil })} bộ nhớ để lưu trữ. Trong trường hợp sai số nhỏ là chấp nhận được, có thể sử dụng sơ đồ Voronoi xấp xỉ, trong đó mỗi điểm nằm trong ô Voronoi của điểm Voronoi gần nhất hoặc xấp xỉ gần nhất[2].